// 单链表(无头)结构：表示队列 
typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;       //队头
	QNode* rear;        //队尾
}Queue;

typedef struct {
    Queue Qa;
    Queue Qb;
} MyStack;

// 申请一个节点
static QNode* BuyNode(QDataType data)
{
	QNode* node = (QNode*)malloc(sizeof(QNode));
	if (NULL == node){
		assert(0);
		return NULL;
	}
	node->data = data;
	node->next = NULL;
	return node;
}

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	//逐个节点释放
	while (cur){
		q->front = cur->next;
		free(cur);
		cur = q->front;
	}
	//q->front = NULL;
	q->rear = NULL;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	/*if (q->front){
	return 1;
	}
	return 0;*/
	return NULL == q->front;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* Newnode = BuyNode(data);
	if (QueueEmpty(q)){    //队空时往队头插入
		q->front = Newnode;
	}
	else {         // 队不空时往队尾插入
		q->rear->next = Newnode;
	}
	q->rear = Newnode;
}

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	if (!QueueEmpty(q)){     //队列不空
		QNode* PopNode = q->front;
		q->front = PopNode->next;
		free(PopNode);
		if (NULL == q->front){
			q->rear = NULL;  //
		}
	}
	return;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(!QueueEmpty(q));     //队列为空
	return q->front->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(!QueueEmpty(q));     //队列为空
	return q->rear->data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	if (!QueueEmpty(q)){  //如果队列不空
		QNode* cur = q->front;
		int size = 0;
		while (cur){
			cur = cur->next;
			size++;
		}
		return size;
	}
	return 0;
}

MyStack* myStackCreate() {
    MyStack* ms = (MyStack*)malloc(sizeof(MyStack));   //申请结构空间
    if(NULL == ms){    //申请失败
        return NULL;
    }
    //分别初始化两个队列
    QueueInit(&ms->Qa);    
    QueueInit(&ms->Qb);
    return ms;
}

//入栈
void myStackPush(MyStack* obj, int x) {
    //哪个队列不空往哪个插入
    if(QueueEmpty(&obj->Qa)){
        QueuePush(&obj->Qb, x);
    }
    else{
        QueuePush(&obj->Qa, x);
    }
}

//出栈
int myStackPop(MyStack* obj) {
    int pop = 0;
    //如果obj->Qa不空，那就先将n-1个元素入到Qb，然后Qa出队
    if(!QueueEmpty(&obj->Qa)){
        while(QueueSize(&obj->Qa)-1){
            QueuePush(&obj->Qb, QueueFront(&obj->Qa));
            QueuePop(&obj->Qa);
        }
        pop = QueueFront(&obj->Qa);
        QueuePop(&obj->Qa);
    }
    else{
        while(QueueSize(&obj->Qb)-1){
            QueuePush(&obj->Qa, QueueFront(&obj->Qb));
            QueuePop(&obj->Qb);
        }
        pop = QueueFront(&obj->Qb);
        QueuePop(&obj->Qb);
    }
    return pop;
}

//获取栈顶元素
int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->Qa)){
        return QueueBack(&obj->Qa);    //Qa不空，获取Qa的队尾
    }
    else{
        return QueueBack(&obj->Qb);
    }
}

//如果栈是空的，返回 true ；否则，返回 false
bool myStackEmpty(MyStack* obj) {
    //两个队列都为空返回true
    return (QueueEmpty(&obj->Qa)) && (QueueEmpty(&obj->Qb));
}


void myStackFree(MyStack* obj) {
    if(obj){
        QueueDestroy(&obj->Qa);
        QueueDestroy(&obj->Qb);
        free(obj);
    }
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/